# -*- coding: utf8 -*-
"""
Hopf algebra : Planar Binary Tree.

AUTHOR:

- Jean-Baptiste Priez
"""
#*****************************************************************************
#       Copyright (C) 2012 Jean-Baptiste Priez <jbp@kerios.fr>,
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    General Public License for more details.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from good_hopf_algebra import GoodHopfAlgebras
from pattern import FundamentalBasis, FundamentalDualBasis, \
    getitem_for_wordlike_indices
from sage.categories.graded_hopf_algebras_with_basis import \
    GradedHopfAlgebrasWithBasis
from sage.categories.realizations import Category_realization_of_parent
from sage.combinat.free_module import CombinatorialFreeModule
from sage.misc.bindable_class import BindableClass
from sage.structure.parent import Parent
from sage.structure.unique_representation import UniqueRepresentation

class CatalanQuasisymmetricFunctions( UniqueRepresentation, Parent ):
    '''
    '''
    def __init__( self, R ):
        '''
        EXAMPLES::

            sage: FQS = FreeQuasisymmetricFunctions(ZZ);FQS
            The Hopf algebra of free quasisymmetric functions over the Integer Ring
        '''
        from sage.categories.all import Rings
        assert( R in Rings() )
        self._base = R
        Parent.__init__( self, category = GoodHopfAlgebras( R ).WithRealizations() )

    def phi( self, indice ):
        '''
        EXAMPLES::

        '''
        return self.indices()( sorted( indice ) )

    def indices( self ):
        '''
        EXAMPLES::

        '''
        from sage.combinat.non_decreasing_parking_function import NonDecreasingParkingFunctions
        return NonDecreasingParkingFunctions()

    def _repr_( self ):
        r"""
        EXAMPLES::

        """
        return "Hopf algebra of Catalan Quasi-Symmetric Functions over the %s" % self.base_ring()

    def a_realization( self ):
        return self.P()

    def dual( self ):
        return self

    def __init_extra__( self ):
        '''
        '''


    _shorthands = set( ['P', 'Q'] )

    class Bases( Category_realization_of_parent ):

        def super_categories( self ):
            R = self.base().base_ring()
            return [self.base().Realizations(),
                    GoodHopfAlgebras( R ).Realizations(),
                    GradedHopfAlgebrasWithBasis( R ).Realizations()]


    class Fundamental( BindableClass, CombinatorialFreeModule ):

        def __init__( self, CQS ):
            CombinatorialFreeModule.__init__( 
                self, CQS.base_ring(), CQS.indices(),
                category = CQS.Bases(),
                prefix = "P", latex_prefix = "\\mathbb{P}",
                bracket = False )

        from pattern import getitem_for_wordlike_indices
        __getitem__ = getitem_for_wordlike_indices

        def product_on_basis( self, ndpf1, ndpf2 ):
            r"""
            The product of the P basis : shuffle of tree

            TESTS::
            
                sage: P = CQSym(QQ).P()
                sage: P[1,1,1] * P[1]
                P[1, 1, 1, 4]
                sage: P[1,2,3,3] * P[1,1,3]
                P[1, 2, 3, 3, 5, 5, 7]
            """
            return self.monomial( self.indices()( ndpf1 + [p + len( ndpf1 ) for p in ndpf2] ) )

        def coproduct_on_basis( self, ndpf ):
            r"""
            The coproduct of the H basis

            TESTS::

                sage: P = CQSym(QQ).P()
                sage: P[1,1,2,4].coproduct()
                P[] # P[1, 1, 2, 4] + P[1] # P[1, 1, 2] + P[1] # P[1, 1, 3] + P[1] # P[1, 2, 3] + P[1, 1] # P[1, 2] + P[1, 1, 2] # P[1] + P[1, 1, 2, 4] # P[] + P[1, 1, 3] # P[1] + P[1, 2] # P[1, 1] + 2*P[1, 2] # P[1, 2] + P[1, 2, 3] # P[1]
            """
            from parking_functions import to_park
            from sage.combinat.subword import Subwords
            def extract_all_sub_ndpf( ndpf ):
                set_of_distinct_subwords = list( Subwords( ndpf ) )
                while len( set_of_distinct_subwords ) > 0:
                    subword = set_of_distinct_subwords.pop()
                    complement = list( ndpf )
                    for l in subword: complement.remove( l )
                    set_of_distinct_subwords.remove( complement )
                    ## .. FIXME:: modify NDPF and PF to recognize some specific PF as NDPF 
                    ndpf1 = self.indices()( list( to_park( subword ) ) )
                    ndpf2 = self.indices()( list( to_park( complement ) ) )
                    while subword in set_of_distinct_subwords:
                        set_of_distinct_subwords.remove( subword )
                        set_of_distinct_subwords.remove( complement )
                    yield ( ndpf1, ndpf2 )
                    yield ( ndpf2, ndpf1 )
            return self.tensor_square().sum_of_monomials( extract_all_sub_ndpf( ndpf ) )

    P = Fundamental

    class FundamentalDual( BindableClass, CombinatorialFreeModule ):

        def __init__( self, CQS ):
            CombinatorialFreeModule.__init__( 
                self, CQS.base_ring(), CQS.indices(),
                category = CQS.Bases(),
                prefix = "M", latex_prefix = "\\mathbb{M}",
                bracket = False )

        def product_on_basis( self, c1, c2 ):
            r'''
            The product of the F basis : concatenation of tree

            EXAMPLES::

                sage: from all import PBT
                sage: Q = PBT(QQ).Q()
                sage: Q[2,1]*Q[3,1,2]
                Q[1, 5, 4, 3, 2] + Q[1, 3, 5, 4, 2] + Q[1, 4, 3, 5, 2] + Q[2, 1, 5, 4, 3] + Q[2, 1, 4, 5, 3] + Q[3, 2, 1, 5, 4] + Q[1, 2, 5, 4, 3] + Q[1, 2, 4, 5, 3] + Q[1, 3, 2, 5, 4] + Q[2, 1, 3, 5, 4]

            .. FIXME::

                improve the product : don't use permutation, compute directly on tree
                ... may be false ...
            '''
            from sage.combinat.words.word import Word
            from sage.sets.set import Set
            c1 = Word( canonical_permutation( c1 ).inverse() )
            c2 = Word( canonical_permutation( c2 ).inverse() )
            ens = c1.shifted_shuffle( c2 )
            return self.sum_of_monomials( [self.phi( Permutation( s ).inverse() ) for s in ens] )

        def coproduct_on_basis( self, p ):
            r"""
            The coproduct of the Q basis : de-shuffle of tree
            
            TESTS::
            
                sage: Q = PBT(QQ).Q()
                sage: Q[[]].coproduct()
                Q[] # Q[]
                sage: Q[1].coproduct()
                Q[] # Q[1] + Q[1] # Q[]
                sage: Q[1,2].coproduct()
                Q[] # Q[1,2] + Q[1] # Q[1] + Q[1,2] # Q[]
                sage: Q[1,2,3].coproduct()
                Q[] # Q[1,2,3] + Q[1] # Q[1,2] + Q[1,2] # Q[1] + Q[1,2,3] # Q[]
                sage: Q[1,3,2].coproduct()
                Q[] # Q[1,3,2] + Q[1] # Q[2,1] + Q[1,2] # Q[1] + Q[1,3,2] # Q[]
    
            EXAMPLES::

                sage: from sage.combinat.pbt.classical import FundamentalDual
                sage: Q = FundamentalDual(QQ)
                sage: Q[6,4,5,2,1,3].coproduct()
                Q[] # Q[2, 1, 4, 6, 5, 3] + Q[1] # Q[1, 3, 5, 4, 2] + Q[2, 1] # Q[2, 4, 3, 1] + Q[2, 1, 3] # Q[1, 3, 2] + Q[2, 1, 4, 3] # Q[2, 1] + Q[2, 1, 4, 5, 3] # Q[1] + Q[2, 1, 4, 6, 5, 3] # Q[]
            """
            def restrict( bt ):
                if bt.is_empty():
                    yield ( bt, bt )
                    return

                for bm, bM in restrict( bt[1] ):
                    yield ( self.indices()( [bt[0], bm] ), bM )
                for bm, bM in restrict( bt[0] ):
                    yield ( bm, self.indices()( [bM, bt[1]] ) )
            return self.tensor_square().sum_of_monomials( restrict( p ) )

    Q = FundamentalDual


